package com.kevinkk.tree;

/**
 * 给出二叉 搜索 树的根节点，该树的节点值各不相同
 * 请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和
 *
 * 常规的中序遍历：左中右，那么BST是一个递增的数组
 * 但是 右中左的遍历方式就会让BST是一个递减的数组
 */

public class ConvertBSTToGreaterTree {
    class Solution {
        TreeNode pre = null;
        public TreeNode convertBST(TreeNode root) {
            traversal(root);
            return root;
        }
        private void traversal(TreeNode root){
            if(root == null) return;
            traversal(root.right);
            if(pre != null){
                root.val += pre.val;
            }
            pre = root;
            traversal(root.left);
        }
    }
}
